#include "MGraph.h"
#include <iostream>
#include <string.h>
#include <list>
using namespace std;

MGraph::MGraph()
{
    //邻接矩阵
    int a[5][5] = {{0,255,1,255,1},{255,0,1,255,255},{1,1,0,1,1},{255,255,1,0,1},{1,255,1,1,0}};
    int v[]={1,2,3,4,5};
    vector<int> t;
    copy(v,v+5,back_inserter(vertex));
    for(int i=0;i<5;++i)
    {
        t.clear();
        copy(a[i],a[i]+5,back_inserter(t));
        arc.push_back(t);
    }

}

MGraph::MGraph(vector<int> &vertex, vector< vector<int> > &arc)
{
    this->vertex = vertex;
    this->arc = arc;
}


int MGraph::prepare()
{
    int size = vertex.size();
    bool v[size];
    memset(v,false,sizeof(bool)*size);
    visited = vector<bool>(v,v+size);

    cout<<"vertexes : ";
    for(int i=0;i<size;++i)
    {
        cout<<vertex[i]<<' ';
    }
    cout<<endl;
    return size;
}

void MGraph::dfs(int i)
{
    visited[i] = true;
    int size = vertex.size();
    cout<<"vertex "<<i<<" : "<<vertex[i]<<endl;
    for(int j=0;j<size;++j)
    {
        if(arc[i][j]==1 && !visited[j])
        {
            dfs(j);
        }
    }
}

void MGraph::DFS()
{
    int size=prepare();

    cout<<"this is Depth First Search"<<endl;

    for(int i=0;i<size;++i) //大循环防止非连通图
    {
        if(!visited[i])
        {
            dfs(i);
        }
    }
    cout<<endl;
}

//广度优先搜索可以求出两点之间的最短路径；
//广度优先搜索更加适合所有边的权值相同的情况
void MGraph::BFS()
{
    int size=prepare();

    cout<<"this is Breadth First Search"<<endl;

    list<int> queue;
    for(int i=0;i<size;++i)
    {
        if(!visited[i])
        {
            visited[i]=true;
            cout<<"vertex "<<i<<" : "<<vertex[i]<<endl;
            queue.push_back(i);
            while(!queue.empty())
            {
                int t = queue.front();
                queue.pop_front();
                for(int j=0;j<size;++j)
                {
                    if(arc[t][j]==1 && !visited[j])
                    {
                        visited[j]=true;
                        cout<<"vertex "<<j<<" : "<<vertex[j]<<endl;
                        queue.push_back(j);

                    }
                }
            }
        }
    }
    cout<<endl;
}

//任意两点之间最终的最短路程
//动态规划的思想
//负权回路的图没有最短路径
void MGraph::floyd_warshall()
{
    int size=prepare();
    vector< vector<int> > e = arc;
    int k, i, j;

    for(k=0;k<size;++k)
    {
        for(int i=0;i<size;++i)
        {
            for(j=0;j<size;++j)
            {
                if(e[i][j]>e[i][k]+e[k][j])
                    e[i][j]=e[i][k]+e[k][j];
            }
        }
    }

    cout<<"this is initial data:"<<endl;
    for(i=0;i<size;++i)
    {
        for(j=0;j<size;++j)
        {
            printf("%4d ",arc[i][j]);
        }
        cout<<endl;
    }

    cout<<"this is Floyd-Warshall:"<<endl;
    for(i=0;i<size;++i)
    {
        for(j=0;j<size;++j)
        {
            printf("%4d ",e[i][j]);
        }
        cout<<endl;
    }
}


//单源最短路径
//时间复杂度是O(n^2)
//对稠密图更有效
//稀疏图：边数M远小于N^2
//稠密图：边数M相对较大的图
void MGraph::Dijkstra(int r, int size)
{
    vector<int> dis = arc[r]; //r号顶点到其余各个顶点的初始路程（估计值）
    int book[size]={0};
    int i,j,u,v,min;


    //核心算法
    for(i=0;i<size-1;++i)
    {
        min = 255;

        //找出当前dis里剩余的最小值
        for(j=0;j<size;++j)
        {
            if(book[j]==0 && dis[j]<min)
            {
                min = dis[j];
                u=j;
            }
        }
        book[u]=1;

        //对各个顶点进行松弛
        for(v=0;v<size;++v)
        {
            if(dis[v]>dis[u]+arc[u][v])
                dis[v]=dis[u]+arc[u][v];
        }
    }

    //打印结果
    for(i=0;i<size;++i)
    {
        printf("%4d ",dis[i]);
    }
    cout<<endl;
}

void MGraph::Dijkstra()
{
    cout<<"\nDijkstra"<<endl;
    int i, size = prepare();
    for(i=0;i<size;++i)
        Dijkstra(i,size);
}
